/**
 * Created by L.jp
 * Description:输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 * User: 86189
 * Date: 2021-12-21
 * Time: 17:22
 */
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //方法一：借助一个节点p,判断list1和list2谁的值小，谁小就把它赋值个节点p,然后继续往后走，当然在这个过程中要构造一个新的链表的表头和表尾
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        /*
        //定义新链表的头结点和尾部节点
        ListNode head = null;
        ListNode tail = null;
        while(list1!=null && list2!=null ) {
            //判断谁小，谁小就赋值给节点p,p相当于是一个起连接作用的节点
            ListNode p = list1.val > list2.val ? list2 : list1;
            if (p == list1) {
                list1 = list1.next;
            } else {
                list2 = list2.next;
            }
            //第一次插入到新的节点到新的链表
            if(head == null){
                head=p;//标记头
                tail=p;//标记尾
            }else{
                //如果不是第一次插入，那么实行尾插到链表的尾节点
                tail.next=p;//尾插
                tail=p;//尾结点后移
            }
        }
        //如果有一个链表已经为空了，那么直接拼接另一个链表后刚刚遍历到的后面的节点
        if(list1==null){
            tail.next = list2;
        }else{
            tail.next=list1;
        }
        return head;*/

        //递归法，因为总是在比较小的那一个节点，然后拼接，一直重复一个动作，所以可以用递归的思想
        ListNode newHead=null;//新的表头
        if(list1.val<list2.val){
             newHead=list1;//谁小就让newHead赋值给谁
            list1=list1.next;//往后走
        }else{
             newHead=list2;
            list2=list2.next;
        }
        newHead.next=Merge(list1,list2);//合并下一个节点，拼接新的节点到当前表头
        return  newHead;//递归最终返回新链表的最初头结点newHead
    }
}
